Sample Programs

Now, we are going to look at a couple of Parallaxis programs. The first shows a parallel sorting algorithm, called ''odd-even transposition sorting'', the second is a parallel version of the ''Sieve of Eratosthenes'' for generating prime numbers.

''Odd-Even Transposition Sorting'' (OETS) is a parallel sorting algorithm that is able to sort n numbers on n PEs in time O(n). The PEs are connected in a bi-directional, open linear list; I/O instructions have been omitted for clarity. In odd iteration steps, the PE-pairs 1-2, 3-4, and so on are compared in parallel while in even iteration steps the pairs 2-3, 4-5, and so on are handled.

	SYSTEM sorting;
	CONST  n = 1000;
	CONFIGURATION list [1..n];
	CONNECTION   left : list[i]  ->  list[i-1].right;
       		     right: list[i]  ->  list[i+1].left;

	SCALAR  k       : integer;
	VECTOR  val,r,l : integer;
       		swap    : boolean;

	BEGIN
	  ... (* read input data *)
	  FOR k:=1 TO n DO
	    PARALLEL
	      PROPAGATE.right(val,l);
	      PROPAGATE.left (val,r);
	      (* l/r now hold the left/right neighbors' values *)
	      swap := false;

	      IF odd(k) THEN  (* compare 1-2, 3-4, ... *)
	        IF odd(dim1) AND (r < val) THEN
	          val  := r;
	          swap := true
	        END
	      ELSE  (* even (k)  compare 2-3, 4-5, ... *)
	        IF even(dim1) AND (r < val) THEN
	          val  := r;
	          swap := true
	        END;
	      END;

	      PROPAGATE.right(swap);
	      IF swap AND (id_no>1) THEN val := l END;
	    ENDPARALLEL
	  END;
	  ... (* write output data *)
	END sorting.

Each PE holds one component of the vector ''val'' that is to be sorted, as well as local copies of each one's left and right neighbor. The marker variable ''swap'' is used for the bookkeeping of swap operations to be finished at the right neighbor PEs. A different approach without marker propagation is possible, but complicates the program.
The program for generating prime numbers is very much straight-forward and does not need a lot of explanation. In each iteration through the ''while''- loop, all multiples of the current number are eliminated in parallel. Execution of the loop continues until no ''candidate'' (on any PE) is left.

	SYSTEM sieve;
	CONFIGURATION list [1000];
	CONNECTION (* none *);

	SCALAR prime: integer;
	VECTOR candidate: boolean;

	BEGIN
	  PARALLEL
	    candidate := id_no >=2;
	    WHILE candidate DO
	      prime:= REDUCE.First(id_no);
	      WriteInt(prime,10); WriteLn;
	      IF id_no MOD prime = 0 THEN candidate:=FALSE END
	    END
	  ENDPARALLEL
	END sieve.